Anvelopă convexă

Anvelopa convexă a mulțimii roșii este mulțimea convexă albastră și roșie.

În geometrie anvelopa convexă sau închiderea convexă a unei forme este cea mai mică mulțime convexă care o cuprinde. Anvelopa convexă poate fi definită fie ca intersecția tuturor mulțimilor convexe care conțin o submulțime dată a spațiului euclidian, fie ca mulțimea tuturor combinațiilor convexe^⁠(d) ale punctelor din submulțimea dată. Pentru o porțiune dintr-un plan, anvelopa convexă poate fi vizualizată printr-un fir de cauciuc întins în jurul porțiunii.

Anvelopa convexă a unei mulțimi deschise este una deschisă, iar anvelopa convexă a unei mulțimi compacte este una compactă. Orice mulțime convexă compactă este anvelopa convexă a punctelor sale extreme^⁠(d). Operatorul „anvelopă convexă” este un exemplu de operator de închidere^⁠(d), iar orice antimatroid^⁠(d) poate fi reprezentat prin aplicarea acestui operator de închidere la o mulțime finită de puncte. Problema algoritmilor de trasare a anvelopei convexe a unei mulțimi finite de puncte din plan sau alte spații euclidiene cu dimensiuni inferioare, precum și problema duală a intersectării semispațiilor, sunt probleme fundamentale ale geometriei algoritmice^⁠(d). Pentru mulțimi situate în plan sau în spațiul tridimensional, acestea pot fi rezolvate cu resurse de calcul de complexitatea $O(n\log n)$, iar pentru dimensiuni superioare, în cel mai rău caz cu resurse de calcul de complexitatea dată de teorema limitei superioare^⁠(d).

La fel ca pentru mulțimi de puncte, anvelopa convexă a fost studiată pentru poligoane simple, mișcare browniană, curbe în spațiu și epigrafele funcțiilor^⁠(d). Anvelopa convexă are aplicații în matematică, statistică, optimizare combinatorie, economie, modelare geometrică și etologie. Structurile conexe includ anvelopa convexă ortogonală^⁠(d), straturile convexe^⁠(d), triangularea Delaunay și pavarea Voronoi^⁠(d).

Definiții

Anvelopa convexă a unei mulțimi mărginite din plan: analogia firului de cauciuc

O mulțime de puncte din spațiul euclidian este definită drept convexă dacă aceasta conține toate segmentele care unesc oricare pereche de puncte ale sale. Anvelopa convexă a unei mulțimi $X$ date poate fi definită prin:

1. Mulțimea convexă minima (unică) conținând $X$
2. Intersecția tuturor mulțimilor convexe conținând $X$
3. Mulțimea tuturor combinațiilor convexe de puncte din $X$
4. Reuniunea tuturor simplexurilor cu vârfuri în $X$

Pentru o mulțime cu frontieră din planul euclidian, cu elemente necoliniare, frontiera anvelopei convexe este linia închisă cu perimetrul minim conținând pe $X$. Se poate imagina întinderea unui fir de cauciuc în jurul întregii mulțimi $S$, iar apoi, eliberându-l, el se strânge; când se oprește, el închide anvelopa convexă a $S$. Această formulare nu se poate generaliza imediat pentru dimensiuni superioare: pentru o mulțime finită de puncte din spațiul tridimensional, o vecinătate a arborelui de acoperire^⁠(d) al punctelor le include cu o suprafață arbitrar de mică, mai mică decât suprafața anvelopei convexe. Cu toate acestea, în dimensiuni superioare, variante ale problemei obstacolelor^⁠(d) de a găsi o suprafață cu energie minimă pe deasupra unei forme date pot avea drept soluție anvelopa convexă.

Pentru obiectele tridimensionale, prima definiție afirmă că anvelopa convexă este cel mai mic posibil volum de delimitare^⁠(d) convex al obiectelor. Definiția pe baza intersecției mulțimilor convexe poate fi extinsă la geometriile neeuclidiene, iar definiția pe baza combinațiilor convexe poate fi extinsă la un spațiu vectorial real sau la un spațiu afin oarecare; anvelopa convexă poate fi generalizată abstract în cadrul matroizilor orientați^⁠(d).

Echivalența definițiilor

Anvelopa convexă tridimensională a unei mulțimi grupate de 120 de puncte

Nu este evident că prima definiție are sens: de ce trebuie ca mulțimea convexă care cuprinde $X$ să fie minimă și de ce este ea unică? Definiția a doua, intersecția tuturor mulțimilor convexe care conțin $X$, este bine definită. Ea este o submulțime a oricărei alte mulțimi convexe $Y$ care conțin $X$, deoarece $Y$ este inclusă în mulțimile care se intersectează. Ca urmare, ea este exact unica mulțime convexă minimă care conține $X$. Prin urmare, primele două definiții sunt echivalente.

Fiecare mulțime convexă care conține $X$ trebuie (presupunând că este convexă) să conțină toate combinațiile convexe de puncte din $X$, astfel toate combinațiile convexe sunt conținute în intersecția tuturor mulțimilor convexe care conțin $X$. Invers, mulțimea tuturor combinațiilor convexe este ea însăși o mulțime convexă care conține $X$, deci conține și intersecția tuturor mulțimilor convexe care conțin $X$, prin urmare a doua și a treia definiție sunt echivalente.

În fapt, conform teoremei Carathéodory^⁠(d), dacă $X$ este o submulțime a spațiului euclidian $d$-dimensional, orice combinație convexă a unui număr finit de puncte din $X$ este și o combinație convexă în $d+1$ a punctelor din $X$. Mulțimea combinațiilor convexe ale unui $(d+1)$-tuplu^{⁠(en)[traduceți]} de puncte este un simplex; în plan el este un triunghi, iar în spațiul tridimensional este un tetraedru. Prin urmare, orice combinație convexă de puncte din $X$ aparține unui simplex, ale cărui vârfuri aparțin lui $X$, iar a treia și a patra definiție sunt echivalente.

Anvelopele de sus și de jos

Pentru calcule, uneori anvelopa convexă este împărțită în două părți. În două dimensiuni, anvelopa convexă este uneori împărțită în două părți, în anvelopa „de sus” și cea „de jos” („sus” și „jos” în sensul foii de hârtie pe care este desenată), întinzându-se între punctele cel mai „din stânga” și cel mai „din dreapta” (tot în sensul foii de hârtie) ale figurii. Mai general, pentru corpurile convexe în orice dimensiune se poate împărți corpul în zone orientate „în sus”, respectiv „în jos” (în sensul cum este privit un corp în mod obișnuit), figura de separație fiind definită de punctele care apar ca extreme în proiecția ortogonală în direcția verticală. Pentru corpurile tridimensionale, părțile orientate în sus și în jos ale frontierei formează discuri topologice. Ideea de partiționare a corpului în două zone provine dintr-o variantă eficientă a algoritmului Graham.

Proprietăți topologice

Anvelope închise și deschise

Anvelopa convexă închisă este închiderea^⁠(d) anvelopei convexe, iar anvelopa convexă deschisă este interiorul anvelopei convexe.

Anvelopa convexă închisă a $X$ este intersecția tuturor semispațiilor care conțin $X$. Dacă anvelopa convexă a $X$ este deja ea însăși o mulțime închisă (asta se întâmplă, de exemplu, dacă $X$ este o mulțime finită sau, mai general, o mulțime compactă), atunci ea este anvelopa convexă închisă. Totuși, o intersecție de spații închise este în sine închisă, așa că atunci când o anvelopă convexă nu este închisă nu poate fi reprezentată în acest fel.

Dacă anvelopa convexă deschisă a mulțimii $X$ este $d$-dimensională, atunci orice punct al anvelopei aparține unei anvelope convexe deschise a cel mult $2d$ puncte ale $X$. Mulțimile vârfurilor unui pătrat, al unui octaedru regulat sau al unui ortoplex sunt exemple în care sunt necesare exact $2d$ puncte.

Conservarea proprietăților topologice

Vrăjitoarea lui Agnesi. Punctele de pe, sau de deasupra curbei roșii sunt un exemplu de mulțime închisă, la care anvelopa convexă este deschisă (vezi semiplanul de deasupra curbei).

Topologic, anvelopa convexă a unei mulțimi deschise este ea însăși una deschisă, iar anvelopa convexă a unei mulțimi compacte ea însăși compactă. Totuși, există mulțimi închise ale căror anvelope convexe nu sunt închise. De exemplu, mulțimea închisă

$\left\{(x,y)\mathop {\bigg |} y\geq {\frac {1}{1+x^{2}}}\right\}$

(mulțimea punctelor aflate deasupra curbei vrăjitoarea lui Agnesi^⁠(d) are semiplanul de deasupra curbei drept anvelopă convexă, deschisă.

Compactitatea anvelopelor convexe ale mulțimilor compacte din spațiile euclidiene, finite dimensional, este generalizată de teorema Krein–Šmulian^⁠(d), conform căreia anvelopa convexă închisă a unei submulțimi slab compacte dintr-un spațiu Banach (o submulțime compactă în sensul topologiei slabe^⁠(d)) este slab compactă.

Puncte extreme

Un punct extrem al unei mulțimi convexe este un punct din mulțime care nu se află pe niciun segment de linie deschisă între oricare alte două puncte ale aceleiași mulțimi. Pentru o anvelopă convexă fiecare punct extrem trebuie să facă parte din mulțimea dată, pentru că altfel nu poate fi format ca o combinație convexă din punctele date. Conform teoremei Kerin – Milman^⁠(d), orice mulțime convexă compactă dintr-un spațiu euclidian (sau mai general într-un spațiu vectorial topologic convex local^⁠(d)) este anvelopa convexă a punctelor sale extreme. Totuși, acest lucru poate să nu fie adevărat pentru mulțimile convexe care nu sunt compacte; de exemplu, întregul plan euclidian și bila unitate deschisă sunt ambele convexe, dar niciunul dintre ele nu are puncte extreme. Teoria Choquet^⁠(d) extinde această teorie de la combinații de puncte extreme convexe finite, la combinații infinite (integrale) în spații mai generale.

Proprietăți geometrice și algebrice

Operator de închidere

Operatorul anvelopă convexă are proprietăți caracteristice unui operator de închidere:

• Este extensiv, în sensul că anvelopa convexă a oricărei mulțimi $X$ este o mulțime care include mulțimea $X$ (este o supramulțime a mulțimii $X$).
• Este nedecrescător, în sensul că pentru oricare două mulțimi $X$ și $Y$ cu $X\subseteq Y$ anvelopa convexă a $X$ este o submulțime a anvelopei convexe a $Y$.
• Este idempotent^⁠(d), în sensul că pentru oricare mulțime $X$ anvelopa convexă a anvelopei convexe a $X$ este identică cu anvelopa convexă a $X$.

Atunci când este aplicat unei mulțimi finite de puncte, acesta este operatorul de închidere al unui antimatroid^⁠(d), antimatroidul interiorului mulțimii de puncte. Astfel fiecare antimatroid poate fi reprezentat prin corpuri convexe de puncte într-un spațiu euclidian de dimensiuni suficient de mari.

Suma Minkowski

Operațiile de construire a anvelopei convexe și a sumei Minkowski^⁠(d) sunt echivalente, în sensul că suma Minkowski a anvelopelor convexe ale mulțimilor dă același rezultat ca și anvelopa convexă a sumei Minkowski a acelorași mulțimi. Aceasta duce la lema Shapley–Folkman^⁠(d), care limitează distanța unei sume Minkowski de anvelopa sa convexă.

Dualitate proiectivă

Operația de construire a anvelopei convexe a unui set de puncte este una dual proiectivă^⁠(d). Adică la construirea intersecției închise a unei familii de semispații, din fiecare pereche duală de semispații care formează spațiul se ia semispațiul care conține originea (sau un alt punct desemnat), nu semispațiul său complementar.

Cazuri speciale

Mulțimi finite de puncte

Anvelopa convexă a unor puncte din plan

Anvelopa convexă a unei mulțimi finite de puncte $S\subset \mathbb {R} ^{d}$ formează în plan un poligon convex, sau, mai general, un politop convex în $\mathbb {R} ^{d}$. Fiecare punct extrem al anvelopei este numit vârf, iar (conform teoremei Krein–Milman^⁠(d)) orice politop convex este anvelopa convexă a vârfurilor sale. El este unicul politop convex ale cărui vârfuri aparțin la $S$ și include toată $S$. Pentru mulțimi de puncte aflate în poziții oarecare, anvelopa convexă este un simplex.

Conform teoremei limitei superioare, numărul de fețe al anvelopei convexe a $n$ puncte în spațiul euclidian $d$-dimensional este $O(n^{\lfloor d/2\rfloor })$. În particular, în două sau trei dimensiuni numărul fețelor este cel mult liniar în $n$.

Poligoane simple

Anvelopa convexă a unui poligon simplu

Anvelopa convexă a unui poligon simplu include poligonul dat și este împărțită în regiuni, una din ele fiind poligonul însuși (albastru în figura alăturată). Alte regiuni, delimitate de lanțul poligonal (frontiera) poligonului și de anvelopa convexă, se numesc buzunare. Calculând aceeași descompunere recursiv pentru fiecare buzunar se formează o descriere ierarhică a poligonului dat, numită arborele diferențelor convexe. Reflectarea unui buzunar peste marginea acestuia de pe anvelopa convexă extinde poligonul simplu dat într-un poligon cu același perimetru și suprafață mai mare, iar teorema Erdős–Nagy^⁠(d) afirmă că acest proces de expansiune se termină în cele din urmă.

Mișcarea browniană

Curba generată de mișcarea browniană în plan, în orice moment fix, are probabilitatea 1 de a avea o anvelopă convexă a cărei limită formează o curbă continuă diferențiabilă. Totuși, pentru orice unghi $\theta$ din intervalul $\pi /2<\theta <\pi$ vor exista momente în timpul mișcării browniene în care particula în mișcare atinge limita corpului convex în vârful unui unghi. Dimensiunea Hausdorff a acestei mulțimi de excepții este (cu probabilitate mare) $1-\pi /2\theta$.

Curbe în spațiu

Un oloid, anvelopa convexă a două cercuri în spațiul tridimensional

În cazul anvelopei convexe a unei curbe din spațiu sau a unei mulțimi finite de curbe din spațiu aflate în poziții oarecare în spațiul tridimensional, părțile frontierei departe de curbe sunt suprafețe desfășurabile și riglate^⁠(d). Un exemplu este oloidul, care este anvelopa convexă a două cercuri din plane perpendiculare, fiecare trecând prin centrul celuilalt. Alt exemplu este sfericonul, anvelopa convexă a două semicercuri în plane perpendiculare având aceeași rază și același centru. Forma acestor anvelope convexe rezultă din teorema de unicitate a lui Alexandrov^⁠(d) și sunt suprafețe obținute prin lipirea a două mulțimi convexe plane (zonele de contact ale celor două componente) cu același perimetru.

Funcții

Anvelopa convexă a unei funcții $f$ pe un spațiu vectorial real este funcția al cărei epigraf este anvelopa convexă de jos a epigrafului său. Este o funcție convexa maximă unică majorată de $f$. Definiția poate fi extinsă la anvelopa convexă a unui set de funcții (obținută din anvelopa convexă a reuniunii epigrafelor lor sau echivalent din minimul lor punctual) și, în această formă, este duală față de operația conjugata convexă^⁠(d).

Calcul

În geometria algoritmică se cunosc o seamă de algoritmi pentru calculul anvelopei convexe a unei mulțimi finite de puncte și pentru alte obiecte geometrice. Calculul anvelopei convexe înseamnă construirea eficientă și neambiguă a reprezentării formei convexe cerute. Rezultatul constă într-o listă de inegalități liniare care descriu fațetele anvelopei, un graf al fațetelor și cu care se învecinează, sau laticea fețelor anvelopei. În două dimensiuni este suficientă lista punctelor care sunt vârfuri în ordinea ciclică în jurul anvelopei.

Pentru anvelopa convexă în două sau trei dimensiuni, complexitatea algoritmilor este dată de numărul de puncte date inițial $n$ și numărul de puncte de pe anvelopa convexă $h$, care poate fi semnificativ mai mic ca $n$. Pentru anvelope în mai multe dimensiuni, numărul fețelor din alte dimensiuni poate și el conta. Algoritmul Graham poate calcula anvelopa convexă a $n$ puncte în plan în timp de ordinul $O(n\log n)$. Pentru puncte în două sau trei dimensiuni se cunosc algoritmi mai complicați, cu performanțe în funcție de numărul de puncte ale soluției, algoritmi care calculează anvelopa convexă în timp de ordinul $O(n\log h)$. Astfel de algoritmi sunt algoritmul Chan și algoritmul Kirkpatrick–Seidel. Pentru dimensiuni $d>3$, timpul de calcul al anvelopei convexe este de ordinul $O(n^{\lfloor d/2\rfloor })$, în funcție de situația cea mai proastă din problemă. Anvelopa convexă a unui poligon simplu din plan poate fi construită în timp de ordin liniar.

Pentru a urmări o mulțime de puncte care se modifică prin adăugări sau eliminări de puncte se poate folosi o structură de date de tip anvelopă convexă dinamică^⁠(d), iar pentru puncte care se mișcă continuu, o structură de date de tip anvelopă convexă cinetică^⁠(d).. Construcția anvelopei convexe este un pas premergător în alți algoritmi, care calculează „lungimea” și „diametrul” mulțimii de puncte.

Structuri conexe

Anvelopă convexă ortogonală		Anvelopă convexă relativă

Și alte forme pot fi definite pentru o mulțime de puncte la fel cum este definită anvelopa convexă: prin supramulțimea minimă cu o anume proprietate, prin intersecția tuturor formelor care conțin punctele, sau prin reuniunea tuturor combinațiilor de puncte de un anumit tip. Exemple:

• Anvelopa afină^⁠(d) este cel mai mic subspațiu afin al spațiului euclidian conținând mulțimea dată, sau reuniunea tuturor combinațiilor de puncte din mulțime.
• Spațiul vectorial generat^⁠(d) este cel mai mic subspațiu liniar al spațiului vectorial care conține mulțimea dată, sau reuniunea tuturor combinațiilor de puncte din mulțime.
• Anvelopa conică^⁠(d) sau anvelopa pozitivă a unei submulțimi a spațiului vectorial este mulțimea tuturor combinațiilor pozitive de puncte din submulțime.
• Anvelopa vizuală^⁠(d) a unui obiect tridimensional, în funcție de câteva puncte de vedere, constă din punctele $p$ astfel încât toate razele care pleacă dintr-un punct de vedere și trec printr-un punct $p$ intersectează obiectul. Echivalent este intersecția conurilor neconvexe generate contururile obiectului obținute din punctele respective de vedere. Este folosită la reconstrucțiile 3D^⁠(d) drept cea mai mare formă care produce aceleași contururi văzute din punctele de vedere date.
• Anvelopa cercuală, sau anvelopa alfa a unei submulțimi din plan este intersecția tuturor discurilor cu o rază dată $1/\alpha$ care conțin submulțimea.
• Anvelopa convexă relativă^⁠(d) a unei submulțimi a unui poligon simplu bidimensional este intersecția tuturor supramulțimilor, unde o mulțime din interiorul aceluiași poligon este relativ convexă dacă conține geodezicele dintre oricare două dintre punctele sale.
• Anvelopa convexă ortogonală, sau anvelopa convexă rectilinie, este intersecția tuturor supramulțimilor ortogonal convexe și a supramulțimilor conectate, în care o mulțime este ortogonal convexă dacă conține toate segmentele dintre perechile de puncte, orientate paralel cu axele.
• Anvelopa convexă ortogonală este un caz particular a unei construcții mai generale, anvelopa injectivă^⁠(d), care poate fi considerată ca fiind cel mai mic spațiu metric injectiv^⁠(d) care conține punctele date din spațiul metric dat.
• Anvelopa convexă olomorfă este o generalizare a conceptelor similare cu varietățile analitice complexe^⁠(d), obținută ca intersecție a mulțimilor de funcții olomorfe care conțin mulțimea dată.

Triangularea Delaunay a unei mulțimi de puncte și a dualului său, diagrama Voronoi^⁠(d), sunt matematic conexe cu anvelopa convexă: triangularea Delaunay a unei mulțimi de puncte din $\mathbb {R} ^{n}$ poate fi văzută ca proiecția anvelopei convexe în $\mathbb {R} ^{n+1}.$ Forma alfa^⁠(d) a unei mulțimi finite de puncte dă o familie înglobată de obiecte geometrice (neconvexe), care, descriu anvelopa unei mulțimi de puncte la diferite niveluri de detaliu. Orice anvelopă alfa este reuniunea unor elemente ale triangulării Delaunay, alese prin compararea razelor cercului circumscris cu parametrul alfa. Mulțimea de puncte însăși este punctul final al acestei familii de anvelope, iar anvelopa sa convexă formează celălalt punct final. Straturile convexe^⁠(d) ale unei mulțimi de puncte sunt o familie de poligoane convexe, cel din exterior fiind anvelopa convexă cu straturile interioare construite recursiv, din puncte care nu sunt vârfuri ale anvelopei convexe.

Aplicații

Anvelopa convexă are aplicații în diferite domenii (vezi mai jos). Astfel, în matematică, anvelopa convexă este folosită pentru a studia polinoamele, vectorii și valorile proprii ale matricilor, și mai multe teoreme din geometria discretă implică anvelopa convexă. Acestea sunt utilizate în statistici robuste drept conturul exterior al adâncimii Tukey^⁠(d), se folosesc la vizualizarea datelor bidimensionale și definesc seturi de risc în luarea deciziilor. Anvelopa convexă a vectorilor indicatori ai soluțiilor în problemele combinatorice este miezul optimizării combinatorii^⁠(d) și în combinatorica poliedrică^⁠(d). În economie, anvelopa convexă poate fi utilizată pentru a aplica metode de convexitate pe piețele neconvexe. În modelarea geometrică, curbele Bézier ajută la netezirea anvelopei convexe, de exemplu la măsurarea carenelor bărcilor. Și în studiul comportamentului animalelor anvelopa convexă este utilizată într-o definiție standard a spațiului vital.

Matematică

Împărțirea a șapte puncte în trei sumulțimi (cele colorate diferit) cu intersecția anvelopelor lor convexe, garantat să existe pentru oricare șapte puncte din plan de teorema Tverberg.

Poligoanele Newton^⁠(d) ale polinoamelor de o singură variabilă și politopurile Newton^⁠(d) ale polinoamelor multivariabilă sunt anvelope convexe ale punctelor derivate din exponenții termenilor din polinom și pot fi folosite pentru a analiza comportamentul asimptotic al polinomului și evaluările rădăcinilor sale. Anvelopa convexă și polinoamele se întâlnesc, de asemenea, în teorema Gauss–Lucas^⁠(d), conform căreia rădăcinile derivatei unui polinom se află toate în anvelopa convexă a rădăcinilor polinomului.

În analiza spectrală^⁠(d), intervalul numeric al unei matrice normale este anvelopa convexă a valorilor proprii ale acesteia. Teorema Russo–Dye^⁠(d) descrie anvelopa convexă a elementelor unitare într-o C*-algebră^⁠(d). În geometria discretă, atât teorema Radon^⁠(d), cât și teorema Tverberg^⁠(d) se referă la existența împărțirii mulțimilor de vârfuri în subseturi cu anvelope convexe care se intersectează.

Definițiile unei mulțimi convexe ca find segmentele dintre punctele sale, astfel încât acestea să fie conținute în interior și a unei anvelope convexe ca intersecție a tuturor supramulțimilor convexe, se aplică atât spațiilor hiperbolice, cât și spațiilor euclidiene. În spațiul hiperbolic este, totuși, posibil să se ia în considerare anvelopele convexe ale mulțimilor de puncte ideale, puncte care nu aparțin spațiului hiperbolic în sine, dar se află la limita unui model al spațiului respectiv. Limitele anvelopelor convexe ale punctelor ideale ale spațiului hiperbolic tridimensional sunt analoage suprafețelor riglate din spațiul euclidian, iar proprietățile lor metrice joacă un rol important în conjectura de geometrizare^⁠(d) în topologia bi- și tridimensională. Anvelopele convexe hiperbolice au fost, de asemenea, utilizate ca parte a calculului triangulațiilor canonice ale varietăților hiperbolice și aplicate pentru a determina echivalența nodurilor.

Vezi și secțiunea mișcarea browniană, pentru aplicațiile anvelopei convexe în acest domeniu și secțiunea curbe în spațiu, pentru aplicațiile în teoria suprafețelor desfășurabile.

Statistică

O corelație. Regiunea umbrită exterioară este anvelopa convexă, iar cea umbrită mai intens din interior este conturul adâncimii Tukey de 50%.

În statistica robustă, anvelopa convexă furnizează o componentă cheie a graficelor de corelație, o metodă pentru vizualizarea împrăștierii unui eșantion bidimensional de puncte. Contururile adâncimilor Tukey formează o familie de mulțimi convexe, având anvelopa convexă spre exterior.

În teoria deciziei^⁠(d) pe baze statistice, mulțimea riscurilor deciziilor aleatorii este anvelopa convexă a punctelor de risc din regulile de decizie deterministe, reguli care stau la baza acestor decizii.

Optimizare combinatorică

În optimizarea combinatorie și combinatorica poliedrică, anvelopa convexă a vectorilor indicatori ai soluțiilor unei probleme combinatorice este obiectul de studiu principal. Dacă pot fi găsite fațetele acetor politopuri, descriind politopurile și intersecțiile semispațiilor, atunci pentru soluțiile optime se pot folosi algoritmii din programarea liniară. În optimizarea multiobiectiv^⁠(d) se folosește și alt tip de anvelopă convexă, anvelopa convexă a vectorilor ponderați ai soluțiilor. Asta poate maximiza combinația aproape convexă a ponderilor, pe baza examinării vârfurilor anvelopei convexe, în loc de a verifica toate soluțiile posibile.

Economie

În modelul Arrow–Debreu^⁠(d) al echilibrului economic general, se presupune că agenții economici au bugetul stabilit și preferințe convexe^⁠(d). Aceste presupuneri ale convexității în economie pot fi folosite pentru a demonstra existența unui echilibru. Dacă datele economice nu sunt convexe, se poate folosi în loc anvelopa lor convexă. Teorema Shapley–Folkman arată că pentru piețe mari această aproximare este bună și duce la un „cvasiechilibru” al pieței neconvexe.

Modelare geometrică

În modelarea geometrică^⁠(d), una din proprietățile esențiale ale curbelor Bézier este că trec prin punctele de control ale anvelopei convexe. De aceea, anvelopa convexă este folosită la detectarea rapidă a punctelor de intersecție ale acestor curbe.

În proiectarea navelor, pentru a verifica dacă acestea corespund poligonului secțiunilor din proiect se folosește măsurarea anvelopei convexe a secțiunilor transversale ale carenei, metodă bună și în cazul carenelor care au părți concave.

Etologie

Anvelopa convexă este cunoscută în etologie ca poligonul convex minim în studiul comportamentului animalului. Este o abordare clasică, deși poate simplistă, în estimarea spațiului vital al unui animal, pe baza punctelor în care animalul a fost observat. Excepțiile pot face ca poligonul convex minim să fie excesiv de mare, ceea ce a motivat abordări relaxate. Acestea conțin doar un subset de observații, de exemplu, alegând unul dintre straturile convexe care este aproape de procentul țintă al eșantioanelor, sau metoda poligonului convex local prin combinarea poligoanelor convexe conform algoritmului celor k cei mai apropiați vecini^⁠(d).

Fizică cuantică

În fizica cuantică, spațiul stărilor^⁠(d) oricărui sistem cuantic — mulțimea stărilor cuantice în care se poate afla sistemul — este anvelopa convexă a punctelor extreme definite drept stări pure, iar interiorul ei drept stări mixte. Teorema Gisin-Hughston-Jozsa-Wootters^⁠(d) arată că orice stare mixtă poate fi exprimată în mai multe feluri, ca o combinație convexă de stări pure.

Istoric

Anvelopa convexă de jos a punctelor din plan a apărut, sub forma unui poligon Newton, într-o scrisoare din 1676 a lui Isaac Newton către Henry Oldenburg. Termenul de „anvelopă convexă” a apărut inițial, în 1922, în recenziile lui Hans Rademacher asupra lucrărilor lui Dénes Kőnig. Conform lui Lloyd Dines, din 1938 termenul de „anvelopă convexă” a devenit standard. Dines a adăugat că după părerea lui expresia este nefericită, deoarece înțelesul comun pentru „anvelopă” sugerează că s-ar referi doar la suprafața formei, în timp ce în realitate se referă și la interiorul ei.

Bibliografie

• Andrew, A. M. (1979), „Another efficient algorithm for convex hulls in two dimensions”, Information Processing Letters, 9 (5): 216–219, doi:10.1016/0020-0190(79)90072-3 
• Artin, Emil (1967), „2.5. Newton's Polygon”, Algebraic Numbers and Algebraic Functions, Gordon and Breach, pp. 37–43, MR 0237460 
• Auel, Asher (2019), „The mathematics of Grace Murray Hopper” (PDF), Notices of the American Mathematical Society, 66 (3): 330–340, MR 3889348 
• Avis, David; Bremner, David; Seidel, Raimund (1997), „How good are convex hull algorithms?”, Computational Geometrie, 7 (5-6): 265–301, doi:10.1016/S0925-7721(96)00023-5, MR 1447243 
• Bárány, Imre; Katchalski, Meir; Pach, János (1982), „Quantitative Helly-type theorems”, Proceedings of the American Mathematical Society, 86 (1): 109–114, doi:10.2307/2044407, MR 0663877 
• Basch, Julien; Guibas, Leonidas J.; Hershberger, John (1999), „Data structures for mobile data”, Journal of Algorithms, 31 (1): 1–28, CiteSeerX 10.1.1.134.6921 , doi:10.1006/jagm.1998.0988, MR 1670903 
• Birkhoff, Garrett (1935), „Integration of functions with values in a Banach space”, Transactions of the American Mathematical Society, 38 (2): 357–378, doi:10.2307/1989687, MR 1501815 
• Brown, K. Q. (1979), „Voronoi diagrams from convex hulls”, Information Processing Letters, 9 (5): 223–228, doi:10.1016/0020-0190(79)90074-7 
• de Berg, M.; van Kreveld, M.; Overmars, Mark; Schwarzkopf, O. (2008), Computational Geometrie: Algorithms and Applications (ed. 3rd), Springer 
• Chan, Timothy M. (2012), „Three problems about dynamic convex hulls”, International Journal of Computational Geometrie and Applications, 22 (4): 341–364, doi:10.1142/S0218195912600096, MR 2994585 
• Chang, J. S.; Yap, C.-K. (1986), „A polynomial solution for the potato-peeling problem”, Discrete & Computational Geometrie, 1 (2): 155–182, doi:10.1007/BF02187692 , MR 0834056 
• Chazelle, Bernard (1985), „On the convex layers of a planar set”, IEEE Transactions on Information Theory, 31 (4): 509–517, doi:10.1109/TIT.1985.1057060, MR 0798557 
• Chazelle, Bernard (1993), „An optimal convex hull algorithm in any fixed dimension” (PDF), Discrete & Computational Geometrie, 10 (1): 377–409, CiteSeerX 10.1.1.113.8709 , doi:10.1007/BF02573985 
• Chen, Qinyu; Wang, Guozhao (martie 2003), „A class of Bézier-like curves”, Computer Aided Geometric Design, 20 (1): 29–39, doi:10.1016/s0167-8396(03)00003-7 
• Cranston, M.; Hsu, P.; March, P. (1989), „Smoothness of the convex hull of planar Brownian motion”, Annals of Probability, 17 (1): 144–150, JSTOR 2244202, MR 0972777 
• Demaine, Erik D.; Gassend, Blaise; O'Rourke, Joseph; Toussaint, Godfried T. (2008), „All polygons flip finitely ... right?”, Surveys on Discrete and Computational Geometrie, Contemporary Mathematics, 453, Providence, Rhode Island: American Mathematical Society, pp. 231–255, doi:10.1090/conm/453/08801, MR 2405683 
• Dines, L. L. (1938), „On convexity”, American Mathematical Monthly, 45 (4): 199–209, doi:10.2307/2302604, JSTOR 2302604, MR 1524247 
• Dirnböck, Hans; Stachel, Hellmuth (1997), „The development of the oloid” (PDF), Journal for Geometrie and Graphics, 1 (2): 105–118, MR 1622664 
• Edelsbrunner, Herbert; Kirkpatrick, David G.; Seidel, Raimund (1983), „On the shape of a set of points in the plane”, IEEE Transactions on Information Theory, 29 (4): 551–559, doi:10.1109/TIT.1983.1056714 
• Epstein, D. B. A.; Marden, A. (1987), „Convex hulls in hyperbolic space, a theorem of Sullivan, and measured pleated surfaces”, În Epstein, D. B. A., Analytical and geometric aspects of hyperbolic space (Coventry/Durham, 1984), London Mathematical Society Lecture Note Series, 111, Cambridge: Cambridge University Press, pp. 113–253, MR 0903852 
• Escobar, Laura; Kaveh, Kiumars (septembrie 2020), „Convex polytopes, algebraic geometrie, and combinatorics” (PDF), Notices of the American Mathematical Society, 67 (8): 1116–1123 
• Gardner, L. Terrell (1984), „An elementary proof of the Russo-Dye theorem”, Proceedings of the American Mathematical Society, 90 (1): 171, doi:10.2307/2044692, MR 0722439 
• Gel'fand, I. M.; Kapranov, M. M.; Zelevinsky, A. V. (1994), „6. Newton Polytopes and Chow Polytopes”, Discriminants, Resultants, and Multidimensional Determinants, Mathematics: Theory & Applications, Birkhäuser, pp. 193–213, doi:10.1007/978-0-8176-4771-1, ISBN 0-8176-3660-9, MR 1264417 
• Getz, Wayne M.; Wilmers, Christopher C. (2004), „A local nearest-neighbor convex-hull construction of home ranges and utilization distributions” (PDF), Ecography, Wiley, 27 (4): 489–505, doi:10.1111/j.0906-7590.2004.03835.x 
• Graham, Ronald L.; Yao, F. Frances (1983), „Finding the convex hull of a simple polygon”, Journal of Algorithms, 4 (4): 324–331, doi:10.1016/0196-6774(83)90013-5, MR 0729228 
• Grünbaum, Branko (2003), Convex Polytopes, Graduate Texts in Mathematics, 221 (ed. 2nd), Springer, ISBN 9780387004242 
• Gustin, William (1947), „On the interior of the convex hull of a Euclidean set”, Bulletin of the American Mathematical Society, 53: 299–301, doi:10.1090/S0002-9904-1947-08787-5 , MR 0020800 
• Harris, Bernard (1971), „Mathematical models for statistical decision theory” (PDF), Optimizing methods in statistics (Proc. Sympos., Ohio State Univ., Columbus, Ohio, 1971), pp. 369–389, MR 0356305, arhivat din original (PDF) la 28 februarie 2021, accesat în 7 ianuarie 2021 
• Herrlich, Horst (1992), „Hyperconvex hulls of metric spaces”, Proceedings of the Symposium on General Topology and Applications (Oxford, 1989), Topology and its Applications, 44 (1-3): 181–187, doi:10.1016/0166-8641(92)90092-E, MR 1173256 
• Johnson, Charles R. (1976), „Normality and the numerical range”, Linear Algebra and its Applications, 15 (1): 89–94, doi:10.1016/0024-3795(76)90080-x , MR 0460358 
• Kashiwabara, Kenji; Nakamura, Masataka; Okamoto, Yoshio (2005), „The affine representation theorem for abstract convex geometries”, Computational Geometrie, 30 (2): 129–144, CiteSeerX 10.1.1.14.4965 , doi:10.1016/j.comgeo.2004.05.001, MR 2107032 
• Katoh, Naoki (1992), „Bicriteria network optimization problems”, IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, E75-A: 321–329 
• Kernohan, Brian J.; Gitzen, Robert A.; Millspaugh, Joshua J. (2001), „Analysis of animal space use and movements”, În Millspaugh, Joshua; Marzluff, John M., Radio Tracking and Animal Populations, Academic Press, ISBN 9780080540221 
• Kirkpatrick, K. A. (2006), „The Schrödinger–HJW theorem”, Foundations of Physics Letters, 19 (1): 95–102, arXiv:quant-ph/0305068 , doi:10.1007/s10702-006-1852-1 
• Kiselman, Christer O. (2002), „A semigroup of operators in convexity theory”, Transactions of the American Mathematical Society, 354 (5): 2035–2053, doi:10.1090/S0002-9947-02-02915-X , MR 1881029 
• Knuth, Donald E. (1992), Axioms and Hulls, Lecture Notes in Computer Science, 606, Heidelberg: Springer-Verlag, doi:10.1007/3-540-55611-7, ISBN 3-540-55611-7, MR 1226891, arhivat din original la 20 iunie 2017, accesat în 7 ianuarie 2021 
• Kőnig, Dénes (decembrie 1922), „Über konvexe Körper”, Mathematische Zeitschrift, 14 (1): 208–210, doi:10.1007/bf01215899 ; see also review by Hans Rademacher (1922), Format:JFM
• Krein, Mark; Milman, David (1940), „On extreme points of regular convex sets”, Studia Mathematica, 9: 133–138 
• Krein, M.; Šmulian, V. (1940), „On regularly convex sets in the space conjugate to a Banach space”, Annals of Mathematics, Second Series, 41: 556–583, doi:10.2307/1968735, hdl:10338.dmlcz/100106 , JSTOR 1968735, MR 0002009 
• Laurentini, A. (1994), „The visual hull concept for silhouette-based image understanding”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 16 (2): 150–162, doi:10.1109/34.273735 
• Lay, Steven R. (1982), Convex Sets and their Applications, John Wiley & Sons, ISBN 0-471-09584-2, MR 0655598 
• Lee, D. T. (1983), „On finding the convex hull of a simple polygon”, International Journal of Computer and Information Sciences, 12 (2): 87–98, doi:10.1007/BF00993195, MR 0724699 
• Mason, Herbert B. (1908), Encyclopaedia of Ships and Shipping, p. 698 
• McCallum, Duncan; Avis, David (1979), „A linear algorithm for finding the convex hull of a simple polygon”, Information Processing Letters, 9 (5): 201–206, doi:10.1016/0020-0190(79)90069-3, MR 0552534 
• Newton, Isaac (24 octombrie 1676), „Letter to Henry Oldenburg”, The Newton Project, University of Oxford 
• Nicola, Piercarlo (2000), „General Competitive Equilibrium”, Mainstream Mathematical Economics in the 20th Century, Springer, pp. 197–215, doi:10.1007/978-3-662-04238-0_16 
• Nilsen, Erlend B.; Pedersen, Simen; Linnell, John D. C. (2008), „Can minimum convex polygon home ranges be used to draw biologically meaningful conclusions?”, Ecological Research, 23 (3): 635–639, doi:10.1007/s11284-007-0421-9 
• Oberman, Adam M. (2007), „The convex envelope is the solution of a nonlinear obstacle problem”, Proceedings of the American Mathematical Society, 135 (6): 1689–1694, doi:10.1090/S0002-9939-07-08887-9 , MR 2286077 
• Okon, T. (2000), „Choquet theory in metric spaces”, Zeitschrift für Analysis und ihre Anwendungen, 19 (2): 303–314, doi:10.4171/ZAA/952, MR 1768994 
• Ottmann, T.; Soisalon-Soininen, E.; Wood, Derick (1984), „On the definition and computation of rectilinear convex hulls”, Information Sciences, 33 (3): 157–171, doi:10.1016/0020-0255(84)90025-2 
• Prasolov, Victor V. (2004), „1.2.1 The Gauss–Lucas theorem”, Polynomials, Algorithms and Computation in Mathematics, 11, Springer, pp. 12–13, doi:10.1007/978-3-642-03980-5, ISBN 3-540-40714-6, MR 2082772 
• Pulleyblank, W. R. (1983), „Polyhedral combinatorics”, În Bachem, Achim; Korte, Bernhard; Grötschel, Martin, Mathematical Programming: The State of the Art (XIth International Symposium on Mathematical Programming, Bonn 1982), Springer, pp. 312–345, doi:10.1007/978-3-642-68874-4_13 
• Rappoport, Ari (1992), „An efficient adaptive algorithm for constructing the convex differences tree of a simple polygon”, Computer Graphics Forum, 11 (4): 235–240, doi:10.1111/1467-8659.1140235 
• Reay, John R. (1979), „Several generalizations of Tverberg's theorem”, Israel Journal of Mathematics, 34 (3): 238–244 (1980), doi:10.1007/BF02760885, MR 0570883 
• Rieffel, Eleanor G.; Polak, Wolfgang H. (2011), Quantum Computing: A Gentle Introduction, MIT Press, pp. 215–216, ISBN 978-0-262-01506-6 
• Rockafellar, R. Tyrrell (1970), Convex Analysis, Princeton Mathematical Series, 28, Princeton, N.J.: Princeton University Press, MR 0274683 
• Rossi, Hugo (1961), „Holomorphically convex sets in several complex variables”, Annals of Mathematics, Second Series, 74: 470–493, doi:10.2307/1970292, JSTOR 1970292, MR 0133479 
• Rousseeuw, Peter J.; Ruts, Ida; Tukey, John W. (1999), „The bagplot: A bivariate boxplot”, The American Statistician, 53 (4): 382–387, doi:10.1080/00031305.1999.10474494 
• Sakuma, Itsuo (1977), „Closedness of convex hulls”, Journal of Economic Theory, 14 (1): 223–227, doi:10.1016/0022-0531(77)90095-3 
• Schneider, Rolf (1993), Convex Bodies: The Brunn–Minkowski Theory, Encyclopedia of Mathematics and its Applications, 44, Cambridge: Cambridge University Press, doi:10.1017/CBO9780511526282, ISBN 0-521-35220-7, MR 1216521 
• Seaton, Katherine A. (2017), „Sphericons and D-forms: a crocheted connection”, Journal of Mathematics and the Arts, 11 (4): 187–202, arXiv:1603.08409 , doi:10.1080/17513472.2017.1318512, MR 3765242 
• Sedykh, V. D. (1981), „Structure of the convex hull of a space curve”, Trudy Seminara imeni I. G. Petrovskogo (6): 239–256, MR 0630708 , translated in Journal of Soviet Mathematics 33 (4): 1140–1153, 1986, doi:10.1007/BF01086114
• Sontag, Eduardo D. (1982), „Remarks on piecewise-linear algebra”, Pacific Journal of Mathematics, 98 (1): 183–201, MR 0644949 
• Steinitz, E. (1914), „Bedingt konvergente Reihen und konvexe Systeme. (Fortsetzung)”, Journal für die Reine und Angewandte Mathematik, 144: 1–40, doi:10.1515/crll.1914.144.1, MR 1580890 
• Talman, Louis A. (1977), „Fixed points for condensing multifunctions in metric spaces with convex structure”, Kōdai Mathematical Seminar Reports, 29 (1-2): 62–70, MR 0463985 
• Toussaint, Godfried (1983), „Solving geometric problems with the rotating calipers”, Proceedings of IEEE MELECON '83, Athens, CiteSeerX 10.1.1.155.5671  
• Toussaint, Godfried (1986), „An optimal algorithm for computing the relative convex hull of a set of points in a polygon”, Proceedings of EURASIP, Signal Processing III: Theories and Applications, Part 2, North-Holland, pp. 853–856 
• Weeks, Jeffrey R. (1993), „Convex hulls and isometries of cusped hyperbolic 3-manifolds”, Topology and Its Applications, 52 (2): 127–149, doi:10.1016/0166-8641(93)90032-9, MR 1241189 
• Westermann, L. R. J. (1976), „On the hull operator”, Indagationes Mathematicae, 38 (2): 179–184, doi:10.1016/1385-7258(76)90065-2 , MR 0404097 
• White, F. Puryer (aprilie 1923), „Pure mathematics”, Science Progress in the Twentieth Century, 17 (68): 517–526, JSTOR 43432008 
• Whitley, Robert (1986), „The Kreĭn-Šmulian theorem”, Proceedings of the American Mathematical Society, 97 (2): 376–377, doi:10.2307/2046536, MR 0835903 
• Williams, Jason; Rossignac, Jarek (2005), „Tightening: curvature-limiting morphological simplification”, În Kobbelt, Leif; Shapiro, Vadim, Proceedings of the Tenth ACM Symposium on Solid and Physical Modeling 2005, Cambridge, Massachusetts, USA, June 13-15, 2005, ACM, pp. 107–112, doi:10.1145/1060244.1060257, hdl:1853/3736 
• Worton, Bruce J. (1995), „A convex hull-based estimator of home-range size”, Biometrics, 51 (4): 1206–1215, doi:10.2307/2533254, JSTOR 2533254 

Legături externe

• en Convex hull (română Anvelopa convexă) la Encyclopedia of Mathematics, EMS Press, Springer, 2001
• en Convex Hull, (română Anvelopa convexă) la Mathworld